home *** CD-ROM | disk | FTP | other *** search
/ C++ für Kids / C++ for kids.iso / SETUP / US / CBUILDER / DATA.Z / LIST.H < prev    next >
C/C++ Source or Header  |  1997-02-13  |  24KB  |  840 lines
  1. #ifndef __STD_LIST__
  2. #define __STD_LIST__
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * list - list declarations for the Standard Library
  8.  *
  9.  * $Id: list,v 1.47 1995/09/18 23:31:35 lijewski Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED
  29.  *
  30.  * The software and information contained herein are proprietary to, and
  31.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  32.  * intends to preserve as trade secrets such software and information.
  33.  * This software is furnished pursuant to a written license agreement and
  34.  * may be used, copied, transmitted, and stored only in accordance with
  35.  * the terms of such license and with the inclusion of the above copyright
  36.  * notice.  This software and information or any other copies thereof may
  37.  * not be provided or otherwise made available to any other person.
  38.  *
  39.  * Notwithstanding any other lease or license that may pertain to, or
  40.  * accompany the delivery of, this computer software and information, the
  41.  * rights of the Government regarding its use, reproduction and disclosure
  42.  * are as set forth in Section 52.227-19 of the FARS Computer
  43.  * Software-Restricted Rights clause.
  44.  *
  45.  * Use, duplication, or disclosure by the Government is subject to
  46.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  47.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  48.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  49.  * P.O. Box 2328, Corvallis, Oregon 97339.
  50.  *
  51.  * This computer software and information is distributed with "restricted
  52.  * rights."  Use, duplication or disclosure is subject to restrictions as
  53.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  54.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  55.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  56.  * then the "Alternate III" clause applies.
  57.  *
  58.  **************************************************************************/
  59.  
  60. #include <stdcomp.h>
  61.  
  62. #include <function>
  63. #include <algorith>
  64. #include <iterator>
  65.  
  66. #ifndef Allocator
  67. #define Allocator allocator
  68. #include <memory>
  69. #endif
  70.  
  71. #ifndef list
  72. #define list list
  73. #endif
  74.  
  75. #ifndef RWSTD_NO_NAMESPACE
  76. namespace std {
  77. #endif
  78.  
  79. template <class T>
  80. class list
  81. {
  82.   protected:
  83.  
  84.     typedef Allocator<void>::pointer void_pointer;
  85.  
  86.     struct list_node;
  87.     friend struct list_node;
  88.  
  89.     struct list_node
  90.     {
  91.         void_pointer next;
  92.         void_pointer prev;
  93.         T            data;
  94.     };
  95.  
  96.     Allocator<list_node>  list_node_allocator;
  97.     Allocator<T>          value_allocator;
  98.  
  99.   public:
  100.     //
  101.     // types
  102.     //
  103.     typedef T                                     value_type;
  104.     typedef Allocator<T>                          value_allocator_type;
  105.     typedef Allocator<T>::pointer                 pointer;
  106.     typedef Allocator<T>::reference               reference;
  107.     typedef Allocator<T>::const_reference         const_reference;
  108.     typedef Allocator<list_node>              list_node_allocator_type;
  109.     typedef Allocator<list_node>::pointer         link_type;
  110.     typedef Allocator<list_node>::size_type       size_type;
  111.     typedef Allocator<list_node>::difference_type difference_type;
  112.  
  113.   protected:
  114.  
  115.     static size_type buffer_size ()
  116.     {
  117.         //
  118.         // Each time we allocate memory we reserve space for
  119.         // this many nodes.  This is currently tuned to
  120.         // allocate memory in 1K chunks, except for large objects.
  121.         //
  122.         return sizeof(list_node) >= 1024 ? 1 : 1024 / sizeof(list_node);
  123.     };
  124.  
  125.     struct list_node_buffer;
  126.     friend struct list_node_buffer;
  127.  
  128.     struct list_node_buffer
  129.     {
  130.         void_pointer next_buffer;
  131.         link_type    buffer;
  132.     };
  133.  
  134.   public:
  135.  
  136.     typedef Allocator<list_node_buffer>          buffer_allocator_type;
  137.     typedef Allocator<list_node_buffer>::pointer buffer_pointer;
  138.  
  139.   protected:
  140.  
  141.     Allocator<list_node_buffer>   buffer_allocator;
  142.     buffer_pointer                buffer_list;
  143.     link_type                     free_list;
  144.     link_type                     next_avail;
  145.     link_type                     last;
  146.  
  147.     void add_new_buffer ()
  148.     {
  149.         buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
  150.         tmp->buffer = list_node_allocator.allocate(buffer_size());
  151.         tmp->next_buffer = buffer_list;
  152.         buffer_list = tmp;
  153.         next_avail = buffer_list->buffer;
  154.         last = next_avail + buffer_size();
  155.     }
  156.     void deallocate_buffers ();
  157.     link_type get_node ()
  158.     {
  159.         link_type tmp = free_list;
  160.         return free_list ? (free_list = (link_type)(free_list->next), tmp)
  161.             : (next_avail == last ? (add_new_buffer(), next_avail++)
  162.                : next_avail++);
  163.     }
  164.     void put_node (link_type p) { p->next = free_list; free_list = p; }
  165.  
  166.   protected:
  167.  
  168.     link_type node;
  169.     size_type length;
  170.  
  171.   public:
  172.  
  173.     class iterator;
  174.     class const_iterator;
  175.  
  176.     class iterator : public bidirectional_iterator<T, difference_type>
  177.     {
  178.         friend class list<T>;
  179.         friend class const_iterator;
  180.  
  181.       protected:
  182.  
  183.         link_type node;
  184.         iterator (link_type x) : node(x) {}
  185.  
  186.       public:
  187.  
  188.         iterator () {}
  189.         bool operator== (const iterator& x) const { return node == x.node; }
  190.         reference operator* () const { return (*node).data; }
  191.         iterator& operator++ ()
  192.         {
  193.             node = (link_type)((*node).next); return *this;
  194.         }
  195.         iterator operator++ (int)
  196.         {
  197.             iterator tmp = *this; ++*this; return tmp;
  198.         }
  199.         iterator& operator-- ()
  200.         {
  201.             node = (link_type)((*node).prev); return *this;
  202.         }
  203.         iterator operator-- (int)
  204.         {
  205.             iterator tmp = *this; --*this; return tmp;
  206.         }
  207.     };  // End of definition of iterator class.
  208.  
  209.     class const_iterator : public bidirectional_iterator<T, difference_type>
  210.     {
  211.         friend class list<T>;
  212.  
  213.       protected:
  214.  
  215.         link_type node;
  216.         const_iterator (link_type x) : node(x) {}
  217.  
  218.       public:
  219.  
  220.         const_iterator () {}
  221.         const_iterator (const iterator& x) : node(x.node) {}
  222.         bool operator== (const const_iterator& x) const {return node==x.node;}
  223.         const_reference operator* () const { return (*node).data; }
  224.         const_iterator& operator++ ()
  225.         {
  226.             node = (link_type)((*node).next); return *this;
  227.         }
  228.         const_iterator operator++ (int)
  229.         {
  230.             const_iterator tmp = *this; ++*this; return tmp;
  231.         }
  232.         const_iterator& operator-- ()
  233.         {
  234.             node = (link_type)((*node).prev); return *this;
  235.         }
  236.         const_iterator operator-- (int)
  237.         {
  238.             const_iterator tmp = *this;
  239.             --*this;
  240.             return tmp;
  241.         }
  242.     };  // End of definition of cosnt_iterator class.
  243.  
  244.     typedef reverse_bidirectional_iterator<const_iterator, value_type,
  245.                                            const_reference, difference_type>
  246.             const_reverse_iterator;
  247.     typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  248.                                            difference_type>
  249.             reverse_iterator;
  250.  
  251.